【题解】 [NOI2015]寿司晚宴 状压DP loj2131 | Qiuly's blog!

【题解】 [NOI2015]寿司晚宴 状压DP loj2131

Posted on | Edited on | In | Comments:

首先，两个数不互质同理于两个数的质因子集合没有交集。考虑一下 $n\leq 30$ 的情况，可以发现这里面的质数也只有 $10$ 个，那么我们将每一个寿司分解质因数，然后将质因子压成一个状态。

设 $f[s1][s2]$ 表示小 $\rm{G}$ 吃了的寿司的状态为 $s1$ ，小 $\rm{W}$ 吃了的寿司的状态为 $s2$ 时的方案数。转移的时候枚举寿司，分别判断两个人是否能吃然后转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e2+2;
const int mul=1024;
const int pri[]={0,2,3,5,7,11,13,17,19,23,29};
int n,s[N];ll p,f[2][mul][mul];

namespace OI {
    void pls(ll&x,ll&y) {x+=y;if(x>p)x-=p;}
    template <typename _Tp> inline void IN(_Tp&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
        while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
        if(flag) x=-x;
    }
}using namespace OI;

int main() {
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    IN(n),IN(p);
    for(int i=2;i<=n;++i)
        for(int j=1;j<=10;++j)
            if(!(i%pri[j])) s[i]|=1<<(j-1);
    f[1][0][0]=1;
    for(int i=2;i<=n;++i) {
        int now=i&1,lst=!now;
        memcpy(f[now],f[lst],sizeof(f[lst]));
        for(int s1=0;s1<mul;++s1)for(int s2=0;s2<mul;++s2) {
            if(!f[lst][s1][s2]) continue;
            if(!(s2&s[i])) pls(f[now][s1|s[i]][s2],f[lst][s1][s2]);
            if(!(s1&s[i])) pls(f[now][s1][s2|s[i]],f[lst][s1][s2]);
        }
    }
    long long ans=0;
    for(int s1=0;s1<mul;++s1)
        for(int s2=0;s2<mul;++s2) pls(ans,f[n&1][s1][s2]);
    printf("%lld\n",ans);
    return 0;
}

可以知道 $n\leq 500$ 的时候，每一个数最多带上一个大于等于 $23$ 的质因子。我们首先将所有的寿司分为两类：带了大于等于 $23$ 的质因子的和没带的。

没带的显然可以向上面那样转移。那么带了的呢？这个显然不能压缩吧。

我们考虑将带了同样的大于等于 $23$ 的质因子的分成一组，这一组要不小 $\rm{G}$ 吃小 $\rm{W}$ 不吃，要不小 $\rm{W}$ 吃小 $G$ 不吃。分别讨论即可。

设 $f1[s1][s2]$ 表示这一组是小 $\rm{G}$ 吃时，小 $\rm{G}$ 吃了的寿司的状态为 $s1$ ， 小 $\rm{W}$ 吃了的寿司的状态为 $s2$ 时的方案数。同理，设 $f2[s1][s2]$ 表示这一组是小 $\rm{W}$ 吃时，小 $\rm{G}$ 吃了的寿司的状态为 $s1$ ， 小 $\rm{W}$ 吃了的寿司的状态为 $s2$ 时的方案数。分别转移就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=pos+1;i<=n;++i) { /*枚举这些寿司*/
    if(a[i].t!=a[i-1].t) /*大质因子不同了*/
        memcpy(f1,f,sizeof(f)),memcpy(f2,f,sizeof(f));
    for(int s1=M-1;~s1;--s1)for(int s2=M-1;~s2;--s2) {
        /*倒着枚举所以没用滚动数组*/
        /*所谓的分别转移*/
        if(!(s2&a[i].s)) pls(f1[s1|a[i].s][s2],f1[s1][s2]);
        if(!(s1&a[i].s)) pls(f2[s1][s2|a[i].s],f2[s1][s2]);
    }
    /*这一组结束了，需要合并答案*/
    if(a[i].t!=a[i+1].t||i==n)
        for(int s1=0;s1<M;++s1)for(int s2=0;s2<M;++s2)
            /*因为f1[s1][s2]和f2[s1][s2]都重复算了一遍原来的
            f[s1][s2]，所以减掉后再取膜*/
            f[s1][s2]=(f1[s1][s2]+f2[s1][s2]-f[s1][s2]+p)%p;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=5e2+2;
const int M=256;
const int pri[]={0,2,3,5,7,11,13,17,19};
ll p,f[M][M],f1[M][M],f2[M][M];
struct Node {int t,s;}a[N];
bool cmp(Node a,Node b) {return a.t<b.t;}

namespace OI {
    void pls(ll&x,ll&y) {x+=y;if(x>=p)x%=p;}
    template <typename _Tp> inline void IN(_Tp&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
        while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
        if(flag) x=-x;
    }
}using namespace OI;

int main() {
    int n;IN(n),IN(p);
    for(int i=2;i<=n;++i) {
        a[i].t=i;
        for(int j=1;j<=8;++j)if(!(i%pri[j])) {
            a[i].s|=1<<(j-1),a[i].t/=pri[j];
            while(!(a[i].t%pri[j])) a[i].t/=pri[j];
        }
    }
    f[0][0]=1;
    sort(a+2,a+n+1,cmp);
    int pos=2;
    while(a[pos].t==1) ++pos;--pos;
    for(int i=2;i<=pos;++i) {
        for(int s1=M-1;~s1;--s1)for(int s2=M-1;~s2;--s2) {
            if(!(s2&a[i].s)) pls(f[s1|a[i].s][s2],f[s1][s2]);
            if(!(s1&a[i].s)) pls(f[s1][s2|a[i].s],f[s1][s2]);
        }
    }
    for(int i=pos+1;i<=n;++i) {
        if(a[i].t!=a[i-1].t)
            memcpy(f1,f,sizeof(f)),memcpy(f2,f,sizeof(f));
        for(int s1=M-1;~s1;--s1)for(int s2=M-1;~s2;--s2) {
            if(!(s2&a[i].s)) pls(f1[s1|a[i].s][s2],f1[s1][s2]);
            if(!(s1&a[i].s)) pls(f2[s1][s2|a[i].s],f2[s1][s2]);
        }
        if(a[i].t!=a[i+1].t||i==n)
            for(int s1=0;s1<M;++s1)for(int s2=0;s2<M;++s2)
                f[s1][s2]=(f1[s1][s2]+f2[s1][s2]-f[s1][s2]+p)%p;
    }
    long long ans=0;
    for(int s1=0;s1<M;++s1)
        for(int s2=0;s2<M;++s2) pls(ans,f[s1][s2]);
    printf("%lld\n",(ans+p)%p);
    return 0;
}

本文标题:【题解】 [NOI2015]寿司晚宴 状压DP loj2131

文章作者:Qiuly

发布时间:2019年05月01日 - 00:00

最后更新:2019年05月05日 - 09:22

原始链接:http://qiulyblog.github.io/2019/05/01/[题解]loj2131/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。